import java.io.*;
import java.util.ArrayList;
import java.util.Date;
import java.util.Enumeration;
import java.util.Hashtable;


class Scanner {

    Hashtable<String, DfaNode> nodeIdMap;
    private DfaNode root;
    private String codes;
    private ArrayList<String> tokens;
    private int end;
    private boolean ff = true;
    private boolean lastf = false;


    private DfaNode getNode(String nodeID) {
        DfaNode node = null;
        if (nodeIdMap.get(nodeID) == null) {
            node = new DfaNode(nodeID);
            nodeIdMap.put(nodeID, node);
        }
        return nodeIdMap.get(nodeID);
    }

    private boolean checkCodeFile(File file) {
        java.util.Scanner scan = null;
        String str;
        try {
            scan = new java.util.Scanner(file);
        } catch (FileNotFoundException e) {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }
        while (scan.hasNextLine()) {
            str = scan.nextLine();
            str += " ";
            boolean b = validate(str);
            if (!b) return b;
        }
        return true;

    }

    public Scanner() throws Exception {
        nodeIdMap = new Hashtable<String, DfaNode>();
        tokens = new ArrayList<String>();
        getmap();

        pw = new PrintWriter(new FileWriter("src/Scanner.out",true));
    }

    boolean error = false;
    PrintWriter pw;

    public void scanDocument(String filename) {
        boolean error;
        error = checkCodeFile(new File(filename));
        if (!error) {
            System.out.println("Incorrect Syntax");

        }
        ArrayList<String> strs = getTokens();
        for (String s : strs) {
            System.out.println(s);
        }        
        this.limit = this.tokens.size();
    }

    int index = 0;
    int limit;
    int laindex = 0;

    public String nextToken() {
        laindex = index + 1;
        if (index < limit) {
            return this.tokens.get(index++);
        } else {
            return null;
        }
    }

    public void getmap() {

        String nid = "";
        String[] chd;
        String[] st = new String[]{"1~<,>,=,/,%qm:4;<:5;letter:9;\":11;<:5;space:15;",
                "13~/:6;",
                "9~letter,digit:9;%col:9;^space:10;^=:10;^>:10;^/:10;",
                "11~?\":11;\":12;"};

        for (String str : st) {
            nid = str.split("~")[0];
            chd = str.split("~")[1].split(";");
            DfaNode node = getNode(nid);
            if (root == null) root = node;
            for (int i = 0; i < chd.length; i++) {
                String condition = chd[i].split(":")[0];
                String nextNodeID = chd[i].split(":")[1];
                if (condition.equals("%col")) condition = ":";
                node.addNode(condition, getNode(nextNodeID));
            }

        }

    }

    public boolean hasMoreTokens() {
        return index < limit;
    }

    public void back() {
        this.index--;
    }

    public void resetLookAhead() {
        this.laindex = index;
    }

    public String lookAhead() {
        return this.tokens.get(laindex++);
    }


    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner();
        scanner.scanDocument("src/input.in");
        if (!scanner.error) {
            while (scanner.hasMoreTokens()) {
                scanner.pw.append(scanner.nextToken());
                scanner.pw.append("\n");
            }
        } else {
            scanner.pw.append("Scanning error.");
        }


        scanner.pw.flush();
        scanner.pw.close();
    }

    private boolean validate(String code) {
        this.codes = code;

        int cpos = 0;
        end = 0;
        while (cpos < code.length()) {
            cpos = sequentialCheck(cpos, root, "");
            if (cpos == -1) return false;
        }
        return true;
    }

    public ArrayList<String> getTokens() {
        return tokens;
    }


    private int sequentialCheck(int cpos, DfaNode node, String prevCondition) {

        Enumeration<String> en = node.map.keys();
        String token;

        if (!en.hasMoreElements()) {
            token = codes.substring(end, cpos);
            if (isLookAhead(prevCondition)) {
                token = codes.substring(end, cpos - 1);
            }
            addToken(token);
            end = cpos;
            if (isLookAhead(prevCondition)) {
                end = cpos - 1;
                return cpos - 1;
            }
            return cpos;

        }

        while (en.hasMoreElements()) {
            String condition = en.nextElement();
            if (ff && cpos < codes.length() && codes.charAt(cpos) == '<') ff = false;
            if (ff) {
                if (codes.substring(cpos, codes.length()).contains("<")) {
                    String ccode = codes.substring(cpos, codes.length());
                    token = ccode.substring(0, ccode.indexOf("<"));
                    addToken(token);
                    end = cpos + ccode.indexOf("<");
                    return cpos + ccode.indexOf("<");
                }
                token = codes.substring(cpos, codes.length());
                addToken(token);
                end = cpos;
                return codes.length();
            }
            if (match(condition, codes.charAt(cpos))) {
                return sequentialCheck(cpos + 1, node.map.get(condition), condition);
            }
        }

        return -1;
    }

    private boolean isLookAhead(String condition) {
        if (condition.startsWith("^")) return true;
        return false;
    }

    private void addToken(String token) {
        if (!token.trim().equals("")) {

            if (lastf && ff) {
                String str = tokens.get(tokens.size() - 1);
                tokens.remove(tokens.size() - 1);
                str += token.trim();
                tokens.add(str);
            } else tokens.add(token);

            lastf = ff;
            if (token.equals("<")) ff = false;
            if (token.equals(">")) ff = true;
        }

    }

    private boolean match(String condition, char c) {
        int cint = c;
        if (condition.startsWith("^")) { //lookahead
            condition = condition.substring(1, condition.length());
        }

        if (condition.equals("%qm")) {
            if (c == '?') return true;
            return false;
        } else if (condition.startsWith("?")) {            //not operator
            if (c == condition.charAt(1)) return false;
            return true;
        } else if (condition.equals("digit")) {
            if (cint >= '0' && cint <= '9')
                return true;
            return false;
        } else if (condition.equals("letter")) {
            if ((cint >= 'a' && cint <= 'z') || (cint >= 'A' && cint <= 'Z') || cint == '-') return true;
            return false;
        } else if (condition.equals("space")) {
            if (c == ' ') return true;
            return false;
        } else if (condition.contains(",")) {
            String[] str = condition.split(",");
            for (int i = 0; i < str.length; i++) {
                if (match(str[i], c) == true) return true;
            }
            return false;

        } else if (condition.length() == 1) {
            if (condition.charAt(0) == c) return true;
            return false;
        }
        return false;

    }

  
}
